package sword.chapter12Sort;

/**
 * 数组相对排序
 *
 * 计数排序
 * 数区间0-1000
 * 输入的数组arr1和arr2分别是[2, 3, 3, 7, 3, 9, 2, 1, 7, 2]和[3, 2, 1]，
 * 则arr1排序之后为[3, 3, 3, 2, 2, 2, 1, 7, 7, 9]。
 *
 * 要点
 * 1. 统计被排序arr1中元素出现次数 counts
 * 2. 遍历arr2，获取arr1中元素，并设置新值，更新counts
 * 3. 再次遍历counts中元素
 *
 * @author K
 * @date 2022-01-11 22:12
 */
public class S75RelativeSortArray {

    public static int[] s75(int[] arr1, int[] arr2) {
        int[] counts = new int[1001];
        for (int num : arr1) {
            counts[num]++;
        }

        int i = 0;
        for (int num : arr2) {
            while (counts[num] > 0) {
                arr1[i++] = num;
                counts[num] --;
            }
        }

        for (int num = 0; num < counts.length; num++) {
            while (counts[num] > 0) {
                arr1[i++] = num;
                counts[num] --;
            }
        }

        return arr1;
    }

    public static void main(String[] args) {
        int[] arr1 = new int[]{2, 3, 3, 7, 3, 9, 2, 1, 7, 2};
        int[] arr2 = new int[]{3, 2, 1};
        int[] result = s75(arr1, arr2);
        System.out.println();
    }
}
